package leetcode.code1382;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.tree.TreeNode;

public class Solution {
	List<Integer> nums;

	public TreeNode balanceBST(TreeNode root) {
		nums = new ArrayList<>();
		this.f(root);
		return this.f2(0, nums.size() - 1);
	}

	private TreeNode f2(int l, int r) {
		if (l > r) {
			return null;
		}
		if (l == r) {
			return new TreeNode(nums.get(l));
		}
		int m = ((r - l) >> 1) + l;
		TreeNode ans = new TreeNode(nums.get(m));
		ans.left = this.f2(l, m - 1);
		ans.right = this.f2(m + 1, r);
		return ans;
	}

	private void f(TreeNode root) {
		if (root == null) {
			return;
		}
		this.f(root.left);
		this.nums.add(root.val);
		this.f(root.right);
	}
}
